(0) Obligation:

Clauses:

member(X, .(Y, Xs)) :- member(X, Xs).
member(X, .(X, Xs)).
subset(.(X, Xs), Ys) :- ','(member(X, Ys), subset(Xs, Ys)).
subset([], Ys).
member1(X, .(Y, Xs)) :- member1(X, Xs).
member1(X, .(X, Xs)).
subset1(.(X, Xs), Ys) :- ','(member1(X, Ys), subset1(Xs, Ys)).
subset1([], Ys).

Query: subset(g,g)

(1) PrologToPrologProblemTransformerProof (SOUND transformation)

Built Prolog problem from termination graph ICLP10.

(2) Obligation:

Clauses:

memberA(T42, .(T43, T44)) :- memberA(T42, T44).
memberA(T52, .(T52, T53)).
subsetB(.(T21, T7), .(T22, T23)) :- memberA(T21, T23).
subsetB(.(T21, T7), .(T22, T23)) :- ','(memberA(T21, T23), subsetB(T7, .(T22, T23))).
subsetB(.(T66, T7), .(T66, T67)) :- subsetB(T7, .(T66, T67)).
subsetB([], T73).

Query: subsetB(g,g)

(3) PrologToPiTRSProof (SOUND transformation)

We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes:
subsetB_in: (b,b)
memberA_in: (b,b)
Transforming Prolog into the following Term Rewriting System:
Pi-finite rewrite system:
The TRS R consists of the following rules:

subsetB_in_gg(.(T21, T7), .(T22, T23)) → U2_gg(T21, T7, T22, T23, memberA_in_gg(T21, T23))
memberA_in_gg(T42, .(T43, T44)) → U1_gg(T42, T43, T44, memberA_in_gg(T42, T44))
memberA_in_gg(T52, .(T52, T53)) → memberA_out_gg(T52, .(T52, T53))
U1_gg(T42, T43, T44, memberA_out_gg(T42, T44)) → memberA_out_gg(T42, .(T43, T44))
U2_gg(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → subsetB_out_gg(.(T21, T7), .(T22, T23))
U2_gg(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → U3_gg(T21, T7, T22, T23, subsetB_in_gg(T7, .(T22, T23)))
subsetB_in_gg(.(T66, T7), .(T66, T67)) → U4_gg(T66, T7, T67, subsetB_in_gg(T7, .(T66, T67)))
subsetB_in_gg([], T73) → subsetB_out_gg([], T73)
U4_gg(T66, T7, T67, subsetB_out_gg(T7, .(T66, T67))) → subsetB_out_gg(.(T66, T7), .(T66, T67))
U3_gg(T21, T7, T22, T23, subsetB_out_gg(T7, .(T22, T23))) → subsetB_out_gg(.(T21, T7), .(T22, T23))

The argument filtering Pi contains the following mapping:
subsetB_in_gg(x1, x2)  =  subsetB_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
U2_gg(x1, x2, x3, x4, x5)  =  U2_gg(x2, x3, x4, x5)
memberA_in_gg(x1, x2)  =  memberA_in_gg(x1, x2)
U1_gg(x1, x2, x3, x4)  =  U1_gg(x4)
memberA_out_gg(x1, x2)  =  memberA_out_gg
subsetB_out_gg(x1, x2)  =  subsetB_out_gg
U3_gg(x1, x2, x3, x4, x5)  =  U3_gg(x5)
U4_gg(x1, x2, x3, x4)  =  U4_gg(x4)
[]  =  []

Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog

(4) Obligation:

Pi-finite rewrite system:
The TRS R consists of the following rules:

subsetB_in_gg(.(T21, T7), .(T22, T23)) → U2_gg(T21, T7, T22, T23, memberA_in_gg(T21, T23))
memberA_in_gg(T42, .(T43, T44)) → U1_gg(T42, T43, T44, memberA_in_gg(T42, T44))
memberA_in_gg(T52, .(T52, T53)) → memberA_out_gg(T52, .(T52, T53))
U1_gg(T42, T43, T44, memberA_out_gg(T42, T44)) → memberA_out_gg(T42, .(T43, T44))
U2_gg(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → subsetB_out_gg(.(T21, T7), .(T22, T23))
U2_gg(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → U3_gg(T21, T7, T22, T23, subsetB_in_gg(T7, .(T22, T23)))
subsetB_in_gg(.(T66, T7), .(T66, T67)) → U4_gg(T66, T7, T67, subsetB_in_gg(T7, .(T66, T67)))
subsetB_in_gg([], T73) → subsetB_out_gg([], T73)
U4_gg(T66, T7, T67, subsetB_out_gg(T7, .(T66, T67))) → subsetB_out_gg(.(T66, T7), .(T66, T67))
U3_gg(T21, T7, T22, T23, subsetB_out_gg(T7, .(T22, T23))) → subsetB_out_gg(.(T21, T7), .(T22, T23))

The argument filtering Pi contains the following mapping:
subsetB_in_gg(x1, x2)  =  subsetB_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
U2_gg(x1, x2, x3, x4, x5)  =  U2_gg(x2, x3, x4, x5)
memberA_in_gg(x1, x2)  =  memberA_in_gg(x1, x2)
U1_gg(x1, x2, x3, x4)  =  U1_gg(x4)
memberA_out_gg(x1, x2)  =  memberA_out_gg
subsetB_out_gg(x1, x2)  =  subsetB_out_gg
U3_gg(x1, x2, x3, x4, x5)  =  U3_gg(x5)
U4_gg(x1, x2, x3, x4)  =  U4_gg(x4)
[]  =  []

(5) DependencyPairsProof (EQUIVALENT transformation)

Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem:
Pi DP problem:
The TRS P consists of the following rules:

SUBSETB_IN_GG(.(T21, T7), .(T22, T23)) → U2_GG(T21, T7, T22, T23, memberA_in_gg(T21, T23))
SUBSETB_IN_GG(.(T21, T7), .(T22, T23)) → MEMBERA_IN_GG(T21, T23)
MEMBERA_IN_GG(T42, .(T43, T44)) → U1_GG(T42, T43, T44, memberA_in_gg(T42, T44))
MEMBERA_IN_GG(T42, .(T43, T44)) → MEMBERA_IN_GG(T42, T44)
U2_GG(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → U3_GG(T21, T7, T22, T23, subsetB_in_gg(T7, .(T22, T23)))
U2_GG(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → SUBSETB_IN_GG(T7, .(T22, T23))
SUBSETB_IN_GG(.(T66, T7), .(T66, T67)) → U4_GG(T66, T7, T67, subsetB_in_gg(T7, .(T66, T67)))
SUBSETB_IN_GG(.(T66, T7), .(T66, T67)) → SUBSETB_IN_GG(T7, .(T66, T67))

The TRS R consists of the following rules:

subsetB_in_gg(.(T21, T7), .(T22, T23)) → U2_gg(T21, T7, T22, T23, memberA_in_gg(T21, T23))
memberA_in_gg(T42, .(T43, T44)) → U1_gg(T42, T43, T44, memberA_in_gg(T42, T44))
memberA_in_gg(T52, .(T52, T53)) → memberA_out_gg(T52, .(T52, T53))
U1_gg(T42, T43, T44, memberA_out_gg(T42, T44)) → memberA_out_gg(T42, .(T43, T44))
U2_gg(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → subsetB_out_gg(.(T21, T7), .(T22, T23))
U2_gg(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → U3_gg(T21, T7, T22, T23, subsetB_in_gg(T7, .(T22, T23)))
subsetB_in_gg(.(T66, T7), .(T66, T67)) → U4_gg(T66, T7, T67, subsetB_in_gg(T7, .(T66, T67)))
subsetB_in_gg([], T73) → subsetB_out_gg([], T73)
U4_gg(T66, T7, T67, subsetB_out_gg(T7, .(T66, T67))) → subsetB_out_gg(.(T66, T7), .(T66, T67))
U3_gg(T21, T7, T22, T23, subsetB_out_gg(T7, .(T22, T23))) → subsetB_out_gg(.(T21, T7), .(T22, T23))

The argument filtering Pi contains the following mapping:
subsetB_in_gg(x1, x2)  =  subsetB_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
U2_gg(x1, x2, x3, x4, x5)  =  U2_gg(x2, x3, x4, x5)
memberA_in_gg(x1, x2)  =  memberA_in_gg(x1, x2)
U1_gg(x1, x2, x3, x4)  =  U1_gg(x4)
memberA_out_gg(x1, x2)  =  memberA_out_gg
subsetB_out_gg(x1, x2)  =  subsetB_out_gg
U3_gg(x1, x2, x3, x4, x5)  =  U3_gg(x5)
U4_gg(x1, x2, x3, x4)  =  U4_gg(x4)
[]  =  []
SUBSETB_IN_GG(x1, x2)  =  SUBSETB_IN_GG(x1, x2)
U2_GG(x1, x2, x3, x4, x5)  =  U2_GG(x2, x3, x4, x5)
MEMBERA_IN_GG(x1, x2)  =  MEMBERA_IN_GG(x1, x2)
U1_GG(x1, x2, x3, x4)  =  U1_GG(x4)
U3_GG(x1, x2, x3, x4, x5)  =  U3_GG(x5)
U4_GG(x1, x2, x3, x4)  =  U4_GG(x4)

We have to consider all (P,R,Pi)-chains

(6) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

SUBSETB_IN_GG(.(T21, T7), .(T22, T23)) → U2_GG(T21, T7, T22, T23, memberA_in_gg(T21, T23))
SUBSETB_IN_GG(.(T21, T7), .(T22, T23)) → MEMBERA_IN_GG(T21, T23)
MEMBERA_IN_GG(T42, .(T43, T44)) → U1_GG(T42, T43, T44, memberA_in_gg(T42, T44))
MEMBERA_IN_GG(T42, .(T43, T44)) → MEMBERA_IN_GG(T42, T44)
U2_GG(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → U3_GG(T21, T7, T22, T23, subsetB_in_gg(T7, .(T22, T23)))
U2_GG(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → SUBSETB_IN_GG(T7, .(T22, T23))
SUBSETB_IN_GG(.(T66, T7), .(T66, T67)) → U4_GG(T66, T7, T67, subsetB_in_gg(T7, .(T66, T67)))
SUBSETB_IN_GG(.(T66, T7), .(T66, T67)) → SUBSETB_IN_GG(T7, .(T66, T67))

The TRS R consists of the following rules:

subsetB_in_gg(.(T21, T7), .(T22, T23)) → U2_gg(T21, T7, T22, T23, memberA_in_gg(T21, T23))
memberA_in_gg(T42, .(T43, T44)) → U1_gg(T42, T43, T44, memberA_in_gg(T42, T44))
memberA_in_gg(T52, .(T52, T53)) → memberA_out_gg(T52, .(T52, T53))
U1_gg(T42, T43, T44, memberA_out_gg(T42, T44)) → memberA_out_gg(T42, .(T43, T44))
U2_gg(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → subsetB_out_gg(.(T21, T7), .(T22, T23))
U2_gg(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → U3_gg(T21, T7, T22, T23, subsetB_in_gg(T7, .(T22, T23)))
subsetB_in_gg(.(T66, T7), .(T66, T67)) → U4_gg(T66, T7, T67, subsetB_in_gg(T7, .(T66, T67)))
subsetB_in_gg([], T73) → subsetB_out_gg([], T73)
U4_gg(T66, T7, T67, subsetB_out_gg(T7, .(T66, T67))) → subsetB_out_gg(.(T66, T7), .(T66, T67))
U3_gg(T21, T7, T22, T23, subsetB_out_gg(T7, .(T22, T23))) → subsetB_out_gg(.(T21, T7), .(T22, T23))

The argument filtering Pi contains the following mapping:
subsetB_in_gg(x1, x2)  =  subsetB_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
U2_gg(x1, x2, x3, x4, x5)  =  U2_gg(x2, x3, x4, x5)
memberA_in_gg(x1, x2)  =  memberA_in_gg(x1, x2)
U1_gg(x1, x2, x3, x4)  =  U1_gg(x4)
memberA_out_gg(x1, x2)  =  memberA_out_gg
subsetB_out_gg(x1, x2)  =  subsetB_out_gg
U3_gg(x1, x2, x3, x4, x5)  =  U3_gg(x5)
U4_gg(x1, x2, x3, x4)  =  U4_gg(x4)
[]  =  []
SUBSETB_IN_GG(x1, x2)  =  SUBSETB_IN_GG(x1, x2)
U2_GG(x1, x2, x3, x4, x5)  =  U2_GG(x2, x3, x4, x5)
MEMBERA_IN_GG(x1, x2)  =  MEMBERA_IN_GG(x1, x2)
U1_GG(x1, x2, x3, x4)  =  U1_GG(x4)
U3_GG(x1, x2, x3, x4, x5)  =  U3_GG(x5)
U4_GG(x1, x2, x3, x4)  =  U4_GG(x4)

We have to consider all (P,R,Pi)-chains

(7) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 4 less nodes.

(8) Complex Obligation (AND)

(9) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

MEMBERA_IN_GG(T42, .(T43, T44)) → MEMBERA_IN_GG(T42, T44)

The TRS R consists of the following rules:

subsetB_in_gg(.(T21, T7), .(T22, T23)) → U2_gg(T21, T7, T22, T23, memberA_in_gg(T21, T23))
memberA_in_gg(T42, .(T43, T44)) → U1_gg(T42, T43, T44, memberA_in_gg(T42, T44))
memberA_in_gg(T52, .(T52, T53)) → memberA_out_gg(T52, .(T52, T53))
U1_gg(T42, T43, T44, memberA_out_gg(T42, T44)) → memberA_out_gg(T42, .(T43, T44))
U2_gg(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → subsetB_out_gg(.(T21, T7), .(T22, T23))
U2_gg(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → U3_gg(T21, T7, T22, T23, subsetB_in_gg(T7, .(T22, T23)))
subsetB_in_gg(.(T66, T7), .(T66, T67)) → U4_gg(T66, T7, T67, subsetB_in_gg(T7, .(T66, T67)))
subsetB_in_gg([], T73) → subsetB_out_gg([], T73)
U4_gg(T66, T7, T67, subsetB_out_gg(T7, .(T66, T67))) → subsetB_out_gg(.(T66, T7), .(T66, T67))
U3_gg(T21, T7, T22, T23, subsetB_out_gg(T7, .(T22, T23))) → subsetB_out_gg(.(T21, T7), .(T22, T23))

The argument filtering Pi contains the following mapping:
subsetB_in_gg(x1, x2)  =  subsetB_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
U2_gg(x1, x2, x3, x4, x5)  =  U2_gg(x2, x3, x4, x5)
memberA_in_gg(x1, x2)  =  memberA_in_gg(x1, x2)
U1_gg(x1, x2, x3, x4)  =  U1_gg(x4)
memberA_out_gg(x1, x2)  =  memberA_out_gg
subsetB_out_gg(x1, x2)  =  subsetB_out_gg
U3_gg(x1, x2, x3, x4, x5)  =  U3_gg(x5)
U4_gg(x1, x2, x3, x4)  =  U4_gg(x4)
[]  =  []
MEMBERA_IN_GG(x1, x2)  =  MEMBERA_IN_GG(x1, x2)

We have to consider all (P,R,Pi)-chains

(10) UsableRulesProof (EQUIVALENT transformation)

For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.

(11) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

MEMBERA_IN_GG(T42, .(T43, T44)) → MEMBERA_IN_GG(T42, T44)

R is empty.
Pi is empty.
We have to consider all (P,R,Pi)-chains

(12) PiDPToQDPProof (EQUIVALENT transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(13) Obligation:

Q DP problem:
The TRS P consists of the following rules:

MEMBERA_IN_GG(T42, .(T43, T44)) → MEMBERA_IN_GG(T42, T44)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.

(14) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • MEMBERA_IN_GG(T42, .(T43, T44)) → MEMBERA_IN_GG(T42, T44)
    The graph contains the following edges 1 >= 1, 2 > 2

(15) YES

(16) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

U2_GG(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → SUBSETB_IN_GG(T7, .(T22, T23))
SUBSETB_IN_GG(.(T21, T7), .(T22, T23)) → U2_GG(T21, T7, T22, T23, memberA_in_gg(T21, T23))
SUBSETB_IN_GG(.(T66, T7), .(T66, T67)) → SUBSETB_IN_GG(T7, .(T66, T67))

The TRS R consists of the following rules:

subsetB_in_gg(.(T21, T7), .(T22, T23)) → U2_gg(T21, T7, T22, T23, memberA_in_gg(T21, T23))
memberA_in_gg(T42, .(T43, T44)) → U1_gg(T42, T43, T44, memberA_in_gg(T42, T44))
memberA_in_gg(T52, .(T52, T53)) → memberA_out_gg(T52, .(T52, T53))
U1_gg(T42, T43, T44, memberA_out_gg(T42, T44)) → memberA_out_gg(T42, .(T43, T44))
U2_gg(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → subsetB_out_gg(.(T21, T7), .(T22, T23))
U2_gg(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → U3_gg(T21, T7, T22, T23, subsetB_in_gg(T7, .(T22, T23)))
subsetB_in_gg(.(T66, T7), .(T66, T67)) → U4_gg(T66, T7, T67, subsetB_in_gg(T7, .(T66, T67)))
subsetB_in_gg([], T73) → subsetB_out_gg([], T73)
U4_gg(T66, T7, T67, subsetB_out_gg(T7, .(T66, T67))) → subsetB_out_gg(.(T66, T7), .(T66, T67))
U3_gg(T21, T7, T22, T23, subsetB_out_gg(T7, .(T22, T23))) → subsetB_out_gg(.(T21, T7), .(T22, T23))

The argument filtering Pi contains the following mapping:
subsetB_in_gg(x1, x2)  =  subsetB_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
U2_gg(x1, x2, x3, x4, x5)  =  U2_gg(x2, x3, x4, x5)
memberA_in_gg(x1, x2)  =  memberA_in_gg(x1, x2)
U1_gg(x1, x2, x3, x4)  =  U1_gg(x4)
memberA_out_gg(x1, x2)  =  memberA_out_gg
subsetB_out_gg(x1, x2)  =  subsetB_out_gg
U3_gg(x1, x2, x3, x4, x5)  =  U3_gg(x5)
U4_gg(x1, x2, x3, x4)  =  U4_gg(x4)
[]  =  []
SUBSETB_IN_GG(x1, x2)  =  SUBSETB_IN_GG(x1, x2)
U2_GG(x1, x2, x3, x4, x5)  =  U2_GG(x2, x3, x4, x5)

We have to consider all (P,R,Pi)-chains

(17) UsableRulesProof (EQUIVALENT transformation)

For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.

(18) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

U2_GG(T21, T7, T22, T23, memberA_out_gg(T21, T23)) → SUBSETB_IN_GG(T7, .(T22, T23))
SUBSETB_IN_GG(.(T21, T7), .(T22, T23)) → U2_GG(T21, T7, T22, T23, memberA_in_gg(T21, T23))
SUBSETB_IN_GG(.(T66, T7), .(T66, T67)) → SUBSETB_IN_GG(T7, .(T66, T67))

The TRS R consists of the following rules:

memberA_in_gg(T42, .(T43, T44)) → U1_gg(T42, T43, T44, memberA_in_gg(T42, T44))
memberA_in_gg(T52, .(T52, T53)) → memberA_out_gg(T52, .(T52, T53))
U1_gg(T42, T43, T44, memberA_out_gg(T42, T44)) → memberA_out_gg(T42, .(T43, T44))

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
memberA_in_gg(x1, x2)  =  memberA_in_gg(x1, x2)
U1_gg(x1, x2, x3, x4)  =  U1_gg(x4)
memberA_out_gg(x1, x2)  =  memberA_out_gg
SUBSETB_IN_GG(x1, x2)  =  SUBSETB_IN_GG(x1, x2)
U2_GG(x1, x2, x3, x4, x5)  =  U2_GG(x2, x3, x4, x5)

We have to consider all (P,R,Pi)-chains

(19) PiDPToQDPProof (SOUND transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(20) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U2_GG(T7, T22, T23, memberA_out_gg) → SUBSETB_IN_GG(T7, .(T22, T23))
SUBSETB_IN_GG(.(T21, T7), .(T22, T23)) → U2_GG(T7, T22, T23, memberA_in_gg(T21, T23))
SUBSETB_IN_GG(.(T66, T7), .(T66, T67)) → SUBSETB_IN_GG(T7, .(T66, T67))

The TRS R consists of the following rules:

memberA_in_gg(T42, .(T43, T44)) → U1_gg(memberA_in_gg(T42, T44))
memberA_in_gg(T52, .(T52, T53)) → memberA_out_gg
U1_gg(memberA_out_gg) → memberA_out_gg

The set Q consists of the following terms:

memberA_in_gg(x0, x1)
U1_gg(x0)

We have to consider all (P,Q,R)-chains.

(21) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • SUBSETB_IN_GG(.(T21, T7), .(T22, T23)) → U2_GG(T7, T22, T23, memberA_in_gg(T21, T23))
    The graph contains the following edges 1 > 1, 2 > 2, 2 > 3

  • SUBSETB_IN_GG(.(T66, T7), .(T66, T67)) → SUBSETB_IN_GG(T7, .(T66, T67))
    The graph contains the following edges 1 > 1, 2 >= 2

  • U2_GG(T7, T22, T23, memberA_out_gg) → SUBSETB_IN_GG(T7, .(T22, T23))
    The graph contains the following edges 1 >= 1

(22) YES